package main

import "fmt"

//#link: https://leetcode-cn.com/problems/profitable-schemes/
func main() {
	n, minProfit := 5, 3
	group := []int{2, 2}
	profit := []int{2, 3}
	fmt.Println(profitableSchemes(n, minProfit, group, profit))
}

//dp[i][j]表示i个人获利j利润的数量
func profitableSchemes(n int, minProfit int, group []int, profit []int) int {
	const mod int = 1e9 + 7
	dp := make([][]int, n+1)
	for i := range dp {
		dp[i] = make([]int, minProfit+1)
		//啥也不干
		dp[i][0] = 1
	}
	//从分组去筛选干这份工作的最大值
	for i, member := range group {
		//利润
		earn := profit[i]
		//有足够人可以来做这份工作
		for j := n; j >= member; j-- {
			for k := minProfit; k >= 0; k-- {
				//这份工作可以做的时候
				dp[j][k] = (dp[j][k] + dp[j-member][max(0, k-earn)]) % mod
			}
		}
	}
	return dp[n][minProfit]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
